
import java.util.Iterator;
import java.util.NoSuchElementException;

/*----------------------------------------------------------------
 *  Author:        Siedin Evgen
 *  Written:       24/2/2013
 *  Last updated:  24/2/2013
 *
 *    
 *  Randomized Queue API
 *
 *----------------------------------------------------------------*/
public class RandomizedQueue<Item> implements Iterable<Item> {

   private Item[] items;
   private int size;

   public RandomizedQueue()
   {
      size = 0;
      items = (Item[]) new Object[1];
   }

   public int size()
   {
      return size;
   }

   public boolean isEmpty()
   {
      return size == 0;
   }

   public void enqueue(Item item)
   {
      if (item == null)
      {
         throw new NullPointerException();
      }

      if (items.length == size)
      {
         resize(items.length * 2);
      }

      items[size] = item;
      size++;
   }

   private void resize(int newSize)
   {
      Item[] copy = (Item[]) new Object[newSize];
      for (int i = 0; i < size; i++)
      {
         copy[i] = items[i];
      }
      items = copy;
   }

   public Item dequeue()
   {
      if (isEmpty())
      {
         throw new NoSuchElementException();
      }

      int itemNumber = StdRandom.uniform(size);

      Item item = items[itemNumber];

      if (itemNumber == size - 1)
      {
         items[itemNumber] = null;
      } else
      {
         items[itemNumber] = items[size - 1];
         items[size - 1] = null;
      }

      size--;

      if (size < items.length / 4)
      {
         resize(items.length / 4);
      }

      return item;
   }

   public Item sample()
   {
      if (isEmpty())
      {
         throw new NoSuchElementException();
      }

      int itemIndex = StdRandom.uniform(size);

      return items[itemIndex];
   }

   public Iterator<Item> iterator()
   {
      return new RandomizedQueueIterator();
   }

   private class RandomizedQueueIterator implements Iterator<Item> {

      private int n = 0;
      private int[] indices;

      public RandomizedQueueIterator()
      {
         indices = new int[size];
         for (int i = 0; i < indices.length; i++)
         {
            indices[i] = i;
         }
         StdRandom.shuffle(indices);
      }

      public boolean hasNext()
      {
         return n < size;

      }

      public void remove()
      {
         throw new UnsupportedOperationException();
      }

      public Item next()
      {
         if (!hasNext())
         {
            throw new NoSuchElementException();
         }
         return items[indices[n++]];

      }
   }
}
